package 中等.排序;

import java.util.Arrays;

/**
 * 给定两个字符串 order 和 s 。order 的所有单词都是 唯一 的，
 * 并且以前按照一些自定义的顺序排序。
 * 对 s 的字符进行置换，使其与排序的 order 相匹配。更具体地说，
 * 如果在 order 中的字符 x 出现字符 y 之前，那么在排列后的字符
 * 串中， x 也应该出现在 y 之前。
 * 返回 满足这个性质的 s 的任意排列 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/custom-sort-string
 */
public class 自定义字符串排序_791 {

    public static void main(String[] args) {

        System.out.println(new 自定义字符串排序_791().customSortString3("cbafg", "abcd"));

    }

    /**
     * 自定义冒泡排序
     */
    public String customSortString(String order, String s) {
        int[] weight = new int[26];
        for (int i = 0; i < order.length(); i++) {
            weight[order.charAt(i) - 'a'] = i + 1;
        }
        char[] chars = s.toCharArray();

        bubbleSort(chars, weight);

        return new String(chars);
    }

    private void bubbleSort(char[] chars, int[] weight) {
        for (int right = chars.length - 1; right > 0; right--) {
            boolean hasChange = false;
            for (int i = 0; i < right; i++) {
                if (weight[chars[i] - 'a'] > weight[chars[i + 1] - 'a']) {
                    replace(chars, i, i + 1);
                    hasChange = true;
                }
            }

            if (!hasChange) {
                return;
            }
        }
    }

    private void replace(char[] chars, int i, int j) {
        char charI = chars[i];
        chars[i] = chars[j];
        chars[j] = charI;
    }

    /**
     * api 快速排序
     */
    public String customSortString2(String order, String s) {
        int[] weight = new int[26];
        for (int i = 0; i < order.length(); i++) {
            weight[order.charAt(i) - 'a'] = i + 1;
        }
        char[] chars = s.toCharArray();
        Character[] characters = new Character[s.length()];
        for (int i = 0; i < characters.length; i++) {
            characters[i] = chars[i];
        }

        Arrays.sort(characters, (a, b) -> weight[a - 'a'] - weight[b - 'a']);

        for (int i = 0; i < characters.length; i++) {
            chars[i] = characters[i];
        }

        return new String(chars);
    }

    /**
     * 自定义计数排序
     * 因为 s 中只包含 26 种小写字母，使用计数排序可以降低到 o(n) 的时间复杂度
     */
    public String customSortString3(String order, String s) {
        StringBuilder stringBuilder = new StringBuilder();

        int[] record = new int[26];
        for (char c : s.toCharArray()) {
            record[c - 'a']++;
        }

        for (char c : order.toCharArray()) {
            while (record[c - 'a'] > 0) {
                record[c - 'a']--;
                stringBuilder.append(c);
            }
        }

        for (int i = 0; i < record.length; i++) {
            while (record[i] > 0) {
                record[i]--;
                stringBuilder.append((char) (i + 'a'));
            }
        }

        return stringBuilder.toString();
    }

}
